/*
Manacher算法:
在O(n)时间复杂度求解最长回文子串长度
概念:
1. 回文半径数组radius: 记录每个位置字符为回文中心求出的回文半径长度
2. 最右回文边界R：是这个位置及之前的位置的回文子串，所到达的最右边的地方
3. 最右回文右边界的对称中心C

流程:(i为下一个移动位置)
1. R<i:  暴力扩, radius[i]=1, i++, R++, C++
2. R>i:  分三种: i'为i相对C的对称位置, i'=2*C-i,L为R的关于C对称位置
    -- i'的radius在L内, 则radius[i] = radius[i']
    -- i'的radius在L外, 则radius[i] = R-i+1
    -- i'的radius刚好在L上，radius[i]外扩，更新R和C
 */
/**
 * 给字符串加#
 * @param {string} str
 * @return {string[]}
 */
function _manacherString (str) {
  let result = ''
  for (let i = 0; i < str.length; i++) {
    result += '#'
    result += str.charAt(i)
  }
  result += '#'
  return result.match(/./g)
}

/**
 * Manacher算法
 * @param {string} str
 * @return {number}
 */
function Manacher (str) {
  if (!str || !str.length) {
    return 0
  }
  const chars = _manacherString(str)
  let C = -1
  let R = -1
  let max = -Infinity
  let centerIndex = -1
  const radius = new Array(chars.length)
  for (let i = 0; i < radius.length; i++) {
    radius[i] = R > i ? Math.min(radius[2 * C - i], R - i + 1) : 1
    while (i + radius[i] < chars.length && i - radius[i] > -1) {
      if (chars[i + radius[i]] === chars[i - radius[i]]) {
        radius[i]++
      } else {
        break
      }
    }
    if (i + radius[i] > R) {
      R = i + radius[i] - 1
      C = i
    }
    if (radius[i] > max) {
      max = radius[i]
      centerIndex = i
    }
  }
  console.log(str.substr((centerIndex - max + 1) / 2, max - 1))
  return max - 1
}

console.log(Manacher('abcdcbafabcdck'))
console.log(Manacher('abcdcbafa'))
console.log(Manacher('aba'))
